(1) Field of the Invention
The present invention relates to the field of memory accessing technology for the storage and retrieval of data and/or instructions from a memory unit. Specifically, the present invention relates to the field of memory cache technology employed to increase the speed and efficiency of memory accessing.
(2) Prior Art
Among the many elements of a computer system are found a central processing unit (CPU), memory storage units (which may be RAM or ROM or other), and interface and control logic units that couple the CPU to the memory storage units for accessing and processing of data and instructions. Generally, each time the CPU processes an instruction it must access a memory storage unit to gain desired data for processing or to obtain the execution instruction itself. For whatever reason, the CPU is constantly interfacing with the memory storage units. Recent developments in computer technology have offered a variety of different types of memory storage units which are adapted for different functions and have different characteristics. Specifically, use of a data cache memory unit and associated logic has become extremely popular because of the versatility and efficiency of data accessing offered by the data cache memory.
A data cache is a special purpose memory unit that is designed for special interface with the CPU. The data cache is typically a small sized specially designed memory unit designed for high speed access to the CPU of a microprocessor. Typically the data cache is of limited size because of the constraints of interfacing the cache with the CPU. The cache memory is designed to specially interface with the CPU so that the CPU can access the data of the cache at very high speeds verse the relative long data accessing required of other, external, memory units. Many cache units are located structurally within the chip containing the microprocessor unit for high speed accessing. A cache is filled with data that the CPU will probably execute on a routine or cyclic basis. This data is placed into the cache memory from the external memory (or generated by the CPU and placed into the cache memory) typically during the execution steps of a program. That is, the most recently used data, determined by monitoring the data flow through the program execution, is placed into the cache memory. New data is placed or replaced into the cache and tagged for identification while older data (i.e., data not accessed over a given time period) is slowly "aged out" or removed from the cache. The memory placed within the cache is also tagged with a unique identifier that is related to the effective memory address associated with the data of the external memory unit.
During program execution when the CPU desires to access (i.e. load or store) data to a particular address within the external memory unit, a special cache logic unit first scans the contents of the cache memory unit to determine if the desired address is located within the high speed cache. If so, the data is accessed via the cache utilizing the tag identifier and the position of the data within the cache. In this case external memory access is not required and therefore the delay associated with external memory access is avoided. Each time data is accessed via the cache a significant amount of processing time is saved by avoiding the delay associated with the external memory. Therefore, memory cache operations or "cache operations" refer to the cache procedure and theory discussed above. Cache operations function on the theory that many computer programs frequently utilize only a relatively small number of data addresses on a cyclic basis and those commonly used values will end up located within the high speed cache memory providing efficient access.
In the event that the desired data is determined to be not within the data cache, the cache logic unit will indicate that a "cache miss" has occurred associated with the access instruction (i.e., a miss load or a miss store) and the instruction causing the miss is called the missed instruction. When a cache miss occurs, the desired data must be accessed from, or to, the external memory which is usually not associated with the structural location of the cache memory unit. This accessing to the external memory takes longer than a cache memory access. During the delay, the many prior art CPUs may not issue further instructions while the address in external memory is being accessed associated with the missed instruction due to problems of data inconsistency. These further instructions are called subsequent instructions to the missed instruction.
A prior art cache system is illustrated in the block diagram of FIG. 1.0. The external memory unit 60 is illustrated coupled to interface control unit 14 which provides controlled access to the external memory 60. A high speed limited size cache unit 10 is illustrated coupled to the logic unit 14. The high speed cache unit is coupled to a microprocessor instruction processor 50 via a cache control unit 12 which controls accessing to the cache between microprocessor instructions and determines whether or not data associated with the microprocessor instructions resides in cache or not. The microprocessor instruction processor 50, the logic unit 12 and the high speed cache 10 are all located within the chip of the microprocessor 5. Because of this location, and other special characteristics, the cache memory 10 allows high speed, efficient interface to the microprocessor. After an instruction generating a cache miss is encountered, the instruction is executed through the external memory 60. When the desired data is obtained via the logic unit 14, it is forwarded to the microprocessor unit 50 for processing. The data is also placed into the cache 10 and tagged for subsequent use.